package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/16 9:04
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 */
public class Title17 {

    List<String> result = new ArrayList<>();

    StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        String[] content = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(content, digits, 0);
        return result;
    }

    private void backTracking(String[] content, String s, int index) {
        if (index == s.length()) {
            result.add(sb.toString());
            return;
        }
        //下一层的字符串
        String str = content[s.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backTracking(content, s, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }



    public static List<String> letterCombinations2(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || "".equals(digits)) {
            return result;
        }
        String[] arr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder temp = new StringBuilder();
        backTracking1(result, arr, temp, digits, 0);
        return result;
    }

    /**
     * @param result
     * @param s  "adgi"
     * @param temp
     * @param digits
     * @param cur
     */
    private static void backTracking1(List<String> result, String[] s, StringBuilder temp, String digits, int cur) {
        if (cur == digits.length()) {
            result.add(temp.toString());
            return;
        }
        //当前层的字符串
        String curS = s[digits.charAt(cur) - '0'];
        for (int i = 0; i < curS.length(); i++) {
            temp.append(curS.charAt(i));
            backTracking1(result, s, temp, digits, cur + 1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public static void main(String[] args) {
        letterCombinations2("23");
    }
}
